package main

import (
	"fmt"
	"sync/atomic"
)

type Node struct {
	value interface{}
	next  *Node
}

type LockFreeStack struct {
	top atomic.Pointer[Node]
}

func NewLockFreeStack() *LockFreeStack {
	return &LockFreeStack{}
}

func (s *LockFreeStack) Push(value interface{}) {
	node := &Node{
		value: value,
	}

	for {
		oldTop := s.top.Load()

		node.next = oldTop

		if s.top.CompareAndSwap(oldTop, node) {
			return
		}
	}
}

func (s *LockFreeStack) Pop() (interface{}, bool) {
	for {
		oldTop := s.top.Load()

		if oldTop == nil {
			return nil, false
		}

		newTop := oldTop.next

		if s.top.CompareAndSwap(oldTop, newTop) {
			return oldTop.value, true
		}
	}
}

func main() {
	stack := NewLockFreeStack()

	stack.Push(1)
	stack.Push(2)
	stack.Push(3)

	value, ok := stack.Pop()
	fmt.Println(value, ok)

	value, ok = stack.Pop()
	fmt.Println(value, ok)

	value, ok = stack.Pop()
	fmt.Println(value, ok)

	value, ok = stack.Pop()
	fmt.Println(value, ok)
}
